#ifndef BINARY_TREE_H
#define BINARY_TREE_H

#include <exception>
#include <algorithm>
#include <iostream>
using namespace std;

/**
 * @brief from dsexceptions.h
 * 
 */
class UnderflowException : public std::exception 
{
public:
    const char* what() const throw() {
        return "Underflow Exception: operation resulted in underflow.";
    }
};

class IllegalArgumentException : public std::exception 
{
public:
    const char* what() const throw() {
        return "Illegal Argument Exception: argument passed is illegal.";
    }
};

class ArrayIndexOutOfBoundsException : public std::exception 
{
public:
    const char* what() const throw() {
        return "Array Index Out Of Bounds Exception: invalid array index access.";
    }
};

class IteratorOutOfBoundsException : public std::exception 
{
public:
    const char* what() const throw() {
        return "Iterator Out Of Bounds Exception: Iterator has gone out of bounds.";
    }
};

class IteratorMismatchException : public std::exception 
{
public:
    const char* what() const throw() {
        return "Iterator Mismatch Exception: Iterators mismatch.";
    }
};

class IteratorUninitializedException : public std::exception 
{
public:
    const char* what() const throw() {
        return "Iterator Uninitialized Exception: Iterator has not been correctly initialized.";
    }
};

/**
 * Comparable element：存储节点所含的数据。
 * BinaryNode *left：指向左侧子节点的指针。
 * BinaryNode *right：指向右侧子节点的指针。
 * int height：树中节点的高度。
 * int color：节点的颜色，对于某些类型的二叉树（如红黑树）有用。
 * BinaryNode()：一个空构造函数，将 left 和 right 指针初始化为 nullptr。
 * BinaryNode(const Comparable & theElement, ..)：接收一个 Comparable 对象的常引用，以及指向左右子节点的指针、节点高度和颜色等参数，然后用这些参数初始化对象。
 * 如果不需要颜色/高度信息，可以忽略颜色/高度成员变量，设为default值。
 * @tparam Comparable 
 */
template <typename Comparable>
class BinaryNode 
{
    enum {RED, BLACK};
    
    public:
        Comparable element;
        BinaryNode * left;
        BinaryNode * right;
        BinaryNode() : left{ nullptr }, right{ nullptr } {} // 将成员变量初始化
        int height = 0;
        int color = 0;
        BinaryNode(const Comparable & theElement, BinaryNode *lt = nullptr, BinaryNode *rt = nullptr ,int h = 0, int c = BLACK)
            : element{theElement}, left{lt}, right{rt}, height{h}, color{c} {}
        BinaryNode(Comparable && theElement, BinaryNode *lt = nullptr ,BinaryNode *rt = nullptr ,int h = 0, int c = BLACK)
            : element{std::move(theElement)}, left{lt}, right{rt}, height{h}, color{c} {}
};

template <typename Comparable>
class BinaryTree
{
  public:
    virtual const Comparable & findMin() const = 0;
    virtual const Comparable & findMax() const = 0;
    virtual bool contains(const Comparable & x) const = 0;
    virtual bool isEmpty() const  = 0;
    virtual void printTree(ostream & out = cout) const = 0;
    virtual void makeEmpty() = 0;
    virtual void insert(const Comparable & x) = 0;
    virtual void insert(Comparable && x) = 0;
    virtual void remove(const Comparable & x) = 0;
  protected:
    virtual BinaryNode<Comparable> * clone(BinaryNode<Comparable> * t) const = 0;
    // virtual BinaryNode<Comparable> * find(const Comparable& x, BinaryNode<Comparable> * t) const = 0;
    virtual void insert(const Comparable & x, BinaryNode<Comparable>* & t) = 0;
    virtual void insert(Comparable && x, BinaryNode<Comparable>* & t) = 0;
    virtual bool contains(const Comparable & x, BinaryNode<Comparable>* t) const = 0;
    virtual void remove(const Comparable & x, BinaryNode<Comparable>* & t) = 0;
    virtual BinaryNode<Comparable> * findMin(BinaryNode<Comparable>* t) const = 0;
    virtual BinaryNode<Comparable> * findMax(BinaryNode<Comparable>* t) const = 0;
    virtual void makeEmpty(BinaryNode<Comparable>* & t) = 0;
    virtual void printTree(BinaryNode<Comparable>* t, ostream & out) const = 0;
};

template <typename Comparable>
class BinarySearchTree : public BinaryTree<Comparable>
{
  public:
    BinarySearchTree() : root{nullptr} {} // 拷贝构造函数
    ~BinarySearchTree() {makeEmpty();}  // 析构函数
    BinarySearchTree(const BinarySearchTree & rhs) : root{nullptr} {root = clone(rhs.root);}  // 拷贝构造函数
    BinarySearchTree(BinarySearchTree && rhs) : root{rhs.root} {rhs.root = nullptr;}
    bool isEmpty() const override {return root == nullptr;}
    
    BinarySearchTree & operator=(const BinarySearchTree & rhs)
    {
        BinarySearchTree copy = rhs;
        swap(*this, copy);
        return *this;
    }
    
    BinarySearchTree & operator=(BinarySearchTree && rhs)
    {
        swap(root, rhs.root);       
        return *this;
    }
    
    const Comparable & findMin() const override
    {
        if(isEmpty())
            throw UnderflowException{};
        return findMin(root)->element;
    }
    
    const Comparable & findMax() const override
    {
        if(isEmpty())
            throw UnderflowException{ };
        return findMax(root)->element;
    }
    
    bool contains(const Comparable & x) const override {return contains(x, this->root);}
    
    void printTree(ostream & out = cout) const override 
    {
        if(isEmpty())
            out << "Empty tree" << endl;
        else
            printTree(root, out);
    }

    void makeEmpty() override {makeEmpty(root);}
    void insert(const Comparable & x) override {insert(x, this->root);}
    void insert(Comparable && x) override {insert(std::move(x), this->root);}
    void remove(const Comparable & x) override {remove(x, this->root);}
    // 此处使用 this-> 来明确指出要使用的是成员变量

  protected:
    BinaryNode<Comparable>* root;

    BinaryNode<Comparable>* clone(BinaryNode<Comparable> * t) const override
    {
        if(t == nullptr)
            return nullptr;
        else
            return new BinaryNode<Comparable>{t->element, clone(t->left), clone(t->right)};
    }

    // BinaryNode<Comparable>* find(const Comparable& x, BinaryNode<Comparable> * t) const override
    // {
    //     if (t == nullptr || t->element == x)
    //         return t;
    //     else if( x < t->element)
    //         return find(x, t->left);
    //     else 
    //         return find(x, t->right);
    // }

    void insert(const Comparable & x, BinaryNode<Comparable>* & t) override
    {
        if(t == nullptr)
            t = new BinaryNode<Comparable>(x, nullptr, nullptr);
        else if(x < t->element)
            insert(x, t->left);
        else if(t->element < x)
            insert(x, t->right);
        else
            ;  // Duplicate; do nothing
    }

    void insert(Comparable && x, BinaryNode<Comparable> * & t) override 
    {
        if(t == nullptr)
            t = new BinaryNode<Comparable>{std::move(x), nullptr, nullptr};
        else if(x < t->element)
            insert(std::move(x), t->left);
        else if(t->element < x)
            insert(std::move(x), t->right);
        else
            ;  // Duplicate; do nothing
    }

    bool contains(const Comparable & x, BinaryNode<Comparable> *t) const override 
    {
        // return find(x, t) != nullptr;
        if( t == nullptr )
            return false;
        else if( x < t->element )
            return contains( x, t->left );
        else if( t->element < x )
            return contains( x, t->right );
        else
            return true;    // Match
    }

    void remove(const Comparable & x, BinaryNode<Comparable>* & t) override 
    {
        // BinaryNode<Comparable> * node = find(x,t);
        // if (node == nullptr)
        //     return;
        // else if (node->left != nullptr && node->right != nullptr)
        // {
        //     node->element = findMin(node->right)->element;
        //     remove(node->element, node->right);
        // }
        // else
        // {
        //     BinaryNode<Comparable> *oldNode = node;
        //     node = (node->left != nullptr) ? node->left : node->right;
        //     delete oldNode;
        // }    
        if( t == nullptr )
            return;   // Item not found; do nothing
        if( x < t->element )
            remove( x, t->left );
        else if( t->element < x )
            remove( x, t->right );
        else if( t->left != nullptr && t->right != nullptr ) // Two children
        {
            t->element = findMin( t->right )->element;
            remove( t->element, t->right );
        }
        else
        {
            BinaryNode<Comparable> *oldNode = t;
            t = ( t->left != nullptr ) ? t->left : t->right;
            delete oldNode;
        }    
    }

    BinaryNode<Comparable> * findMin(BinaryNode<Comparable>* t) const override
    {
        if(t != nullptr)
            while(t->left != nullptr)
                t = t->left;
        return t;
    }

    BinaryNode<Comparable> * findMax(BinaryNode<Comparable>* t) const override 
    {
        if(t != nullptr)
            while(t->right != nullptr)
                t = t->right;
        return t;
    }

    void makeEmpty(BinaryNode<Comparable>* & t) override
    {
        if(t != nullptr)
        {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        t = nullptr;
    }

    void printTree(BinaryNode<Comparable> *t, ostream & out) const override 
    {
        if( t != nullptr )
        {
            printTree(t->left, out);
            out << t->element << endl;
            printTree(t->right, out);
        }
    }
    
};

/**
 * @brief 二叉搜索树的子类
 * 提供了一些额外方法以执行节点的旋转操作，这对于某些类型的自平衡二叉搜索树(如AVL树或红黑树)是需要的
 * 
 * @tparam Comparable 
 */
template <typename Comparable>
class BinaryTreeWithRotation : public BinarySearchTree<Comparable>
{
    using BinarySearchTree<Comparable>::isEmpty;     
    public:
        void printTree() const
        {
            if(isEmpty())
                cout << "Empty tree" << endl;
            else
                printTree(this->root);
        }

    protected:
        void printTree(BinaryNode<Comparable> *t) const
        {
            if(t != nullptr)
            {
                printTree(t->left);
                cout << t->element << endl;
                printTree(t->right);
            }
        }

        void rotateWithLeftChild(BinaryNode<Comparable> * & k2)
        {
            BinaryNode<Comparable> *k1 = k2->left;
            k2->left = k1->right;
            k1->right = k2;
            k2 = k1;
        }

        void rotateWithRightChild(BinaryNode<Comparable> * & k1)
        {
            BinaryNode<Comparable> *k2 = k1->right;
            k1->right = k2->left;
            k2->left = k1;
            k1 = k2;
        }

        void doubleWithLeftChild(BinaryNode<Comparable> * & k3)
        {
            rotateWithRightChild(k3->left);
            rotateWithLeftChild(k3);
        }

        void doubleWithRightChild(BinaryNode<Comparable> * & k1)
        {
            rotateWithLeftChild(k1->right);
            rotateWithRightChild(k1);
        }

        /**
         * @brief 这个方法实现了一个后序遍历删除所有节点，回收内存。
         * 这通常在析构函数中调用，以确保所有动态分配的内存都被妥善释放。
         * 后续将在makeEmpty()中使用
         * 
         * @param t 
         */
        void reclaimMemory(BinaryNode<Comparable> *t)
        {
            if(t != t->left)
            {
                reclaimMemory(t->left);
                reclaimMemory(t->right);
                delete t;
            }
        }
};

template <typename Comparable>
class AvlTree : public BinaryTreeWithRotation<Comparable>
{  
    using BinarySearchTree<Comparable>::root;
	using BinarySearchTree<Comparable>::isEmpty;
    using BinarySearchTree<Comparable>::makeEmpty;
    // using BinarySearchTree<Comparable>::find;
    using BinaryTreeWithRotation<Comparable>::rotateWithLeftChild;
    using BinaryTreeWithRotation<Comparable>::rotateWithRightChild;
    using BinaryTreeWithRotation<Comparable>::doubleWithLeftChild;
    using BinaryTreeWithRotation<Comparable>::doubleWithRightChild;
    public:
    using BinarySearchTree<Comparable>::findMin;
        AvlTree() {root = nullptr;}
        ~AvlTree() {makeEmpty();}
        AvlTree(const AvlTree & rhs) {root = clone(rhs.root);}  // 拷贝构造函数
        AvlTree(AvlTree && rhs) {
            root = rhs.root;
            rhs.root = nullptr;
        }
        
        AvlTree & operator=(const AvlTree & rhs)
        {
            AvlTree copy = rhs;
            swap(*this, copy);
            return *this;
        } 

        AvlTree & operator=(AvlTree && rhs)
        {
            swap(root, rhs.root);
            return *this;
        }
        void insert(const Comparable & x) override {insert(x, root);}
        void insert(Comparable && x) override {insert(std::move(x), root);}
        void remove(const Comparable & x) override {remove(x, root);}
        
    protected:
        BinaryNode<Comparable> * clone(BinaryNode<Comparable> * t) const override
        {
            if(t == nullptr)
                return nullptr;
            else
                return new BinaryNode<Comparable>{t->element, clone(t->left), clone(t->right), t->height};
        }

        void insert(const Comparable & x, BinaryNode<Comparable> * & t) override
        {
            if(t == nullptr)
                t = new BinaryNode<Comparable>(x, nullptr, nullptr);
            else if(x < t->element)
                insert(x, t->left);
            else if(t->element < x)
                insert(x, t->right);
            else
                ;  // Duplicate; do nothing
            balance(t);
        }

        void insert(Comparable && x, BinaryNode<Comparable> * & t) override 
        {
            if(t == nullptr)
                t = new BinaryNode<Comparable>{std::move(x), nullptr, nullptr};
            else if(x < t->element)
                insert(std::move(x), t->left);
            else if(t->element < x)
                insert(std::move(x), t->right);
            else
                ;  // Duplicate; do nothing
            balance(t);
        }

        void remove(const Comparable & x, BinaryNode<Comparable> * & t ) override
        {
            // BinaryNode<Comparable> * node = find(x,t);
            // if (node == nullptr)
            //     return;
            // else if (node->left != nullptr && node->right != nullptr)
            // {
            //     node->element = findMin(node->right)->element;
            //     remove(node->element, node->right);
            // }
            // else
            // {
            //     BinaryNode<Comparable> *oldNode = node;
            //     node = (node->left != nullptr) ? node->left : node->right;
            //     delete oldNode;
            // }   
            if( t == nullptr )
                return;   // Item not found; do nothing
            if( x < t->element )
                remove( x, t->left );
            else if( t->element < x )
                remove( x, t->right );
            else if( t->left != nullptr && t->right != nullptr ) // Two children
            {
                t->element = BinarySearchTree<Comparable>::findMin( t->right )->element;
                remove( t->element, t->right );
            }
            else
            {
                BinaryNode<Comparable> *oldNode = t;
                t = ( t->left != nullptr ) ? t->left : t->right;
                delete oldNode;
            } 
            balance(t);
        }

        static const int ALLOWED_IMBALANCE = 1;
        // Assume t is balanced or within one of being balanced
        void balance(BinaryNode<Comparable> * & t)
        {
            if(t == nullptr)
                return;
        
            // 左倾严重
            if(height(t->left) - height(t->right) > ALLOWED_IMBALANCE)
                if(height(t->left->left) >= height(t->left->right))
                    rotateWithLeftChild(t);
                else
                    doubleWithLeftChild(t);
            // 右倾严重
            else if(height(t->right) - height(t->left) > ALLOWED_IMBALANCE)
            {
                if(height(t->right->right) >= height(t->right->left))
                {
                    rotateWithRightChild(t);
                }
                else 
                {
                    doubleWithRightChild(t);
                }
            }
            // 更新height
            t->height = max(height(t->left), height(t->right)) + 1;
        }
        int height( BinaryNode<Comparable> *t ) const
        {
            return t == nullptr ? -1 : t->height;
        }

        int max( int lhs, int rhs ) const
        {
            return lhs > rhs ? lhs : rhs;
        }
};

template <typename Comparable>
class RedBlackTree : public BinaryTreeWithRotation<Comparable>
{
    using BinaryTreeWithRotation<Comparable>::rotateWithLeftChild;
    using BinaryTreeWithRotation<Comparable>::rotateWithRightChild;
    using BinaryTreeWithRotation<Comparable>::doubleWithLeftChild;
    using BinaryTreeWithRotation<Comparable>::doubleWithRightChild;
    using BinaryTreeWithRotation<Comparable>::reclaimMemory;
    public:
        explicit RedBlackTree(const Comparable & negInf)
        {
            nullNode       = new BinaryNode<Comparable>;
            nullNode->left = nullNode->right = nullNode;
            header         = new BinaryNode<Comparable>{negInf};
            header->left   = header->right = nullNode;
        }

        RedBlackTree(const RedBlackTree & rhs)
        {
            nullNode       = new BinaryNode<Comparable>;
            nullNode->left = nullNode->right = nullNode;
            header         = new BinaryNode<Comparable>{rhs.header->element};
            header->left   = nullNode;
            header->right  = clone(rhs.header->right);
        }

        RedBlackTree(RedBlackTree && rhs)
            : nullNode{rhs.nullNode}, header{rhs.header}
        {
            rhs.nullNode = nullptr;
            rhs.header = nullptr;
        }

        ~RedBlackTree()
        {
            makeEmpty();
            delete nullNode;
            delete header;
        }

        RedBlackTree & operator=(const RedBlackTree & rhs)
        {
            RedBlackTree copy = rhs;
            swap(*this, copy);
            return *this;
        }

        RedBlackTree & operator=(RedBlackTree && rhs)
        {
            swap(header, rhs.header);
            swap(nullNode, rhs.nullNode);
            return *this;
        }

        const Comparable & findMin() const
        {
            if(isEmpty())
                throw UnderflowException{};
            BinaryNode<Comparable> *itr = header->right;
            while(itr->left != nullNode)
                itr = itr->left;
            return itr->element;
        }

        const Comparable & findMax() const
        {
            if(isEmpty())
                throw UnderflowException{};
            BinaryNode<Comparable> *itr = header->right;
            while(itr->right != nullNode)
                itr = itr->right;
            return itr->element;
        }

        bool contains(const Comparable & x) const
        {
            nullNode->element = x;
            BinaryNode<Comparable> *curr = header->right;
            for( ; ; )
            {
                if(x < curr->element)
                    curr = curr->left;
                else if(curr->element < x)
                    curr = curr->right;
                else
                    return curr != nullNode;
            }
        }

        bool isEmpty() const {return header->right == nullNode;}

        void makeEmpty()
        {
            if(header == nullptr)
                return;
            reclaimMemory(header->right);
            header->right = nullNode;
        }

        void insert(const Comparable & x)
        {
            current = parent = grand = header;
            nullNode->element = x;
            while(current->element != x)
            {
                great = grand; grand = parent; parent = current;
                current = x < current->element ?  current->left : current->right;
                if(current->left->color == RED && current->right->color == RED)
                    handleReorient(x);
            }
            if(current != nullNode)
                return;
            current = new BinaryNode<Comparable>{x, nullNode, nullNode};
            if(x < parent->element)
                parent->left = current;
            else
                parent->right = current;
            handleReorient(x);
        }

        void remove(const Comparable & item)
        {
            if(header->right == nullNode)
                return;
            current = parent = grand = header;
            nullNode->element = item;
            while(current->element != item)
            {
                great = grand;
                grand = parent;
                parent = current;
                current = item < current->element ? current->left : current->right;
                if(current == nullNode)
                    return; //item not found
            }
            if(current->left == nullNode || current->right == nullNode)
            {
                // No children
                successor = current;
            }
            else 
            {
                // In order successor (right then as far left as possible)
                successor = current->right; 
                while(successor->left != nullNode)
                    successor = successor->left; 
            }
            Comparable removeItem = current->element; 
            current->element = successor->element; 
            current = successor;
            successor = item < parent->element ? parent->left : parent->right;
            // Delete terminal node
            if(successor == parent->left) {
                parent->left = 
                    current->left == nullNode ? current->right : current->left;
            } else {
                parent->right = 
                    current->left == nullNode ? current->right : current->left;
            }
            delete current;
            // Adjust tree
            if(header->right != nullNode)
                header->right->color = BLACK; 
            if(header->right != nullNode && current->color != RED)
                removeAdjustTree(parent);
            return;
        }

        void removeAdjustTree(BinaryNode<Comparable> * t)
        {
            if(t != header)
            {
                if(parent->color == BLACK && sibling->color == RED && sibling->left->color == BLACK && sibling->right->color == BLACK)
                {
                    parent->color = RED;
                    sibling->color = BLACK;
                }
                else
                {
                    if(parent->color == BLACK && sibling->color == BLACK && sibling->left->color == BLACK && sibling->right->color == BLACK)
                    {
                        sibling->color = RED;
                        removeAdjustTree(grand);
                    }
                    else
                    {
                        if(t == parent->left && sibling->color == BLACK && sibling->left->color == RED && sibling->right->color == BLACK)
                        {
                            sibling->color = RED;
                            sibling->left->color = BLACK;
                            rotateWithRightChild(sibling);
                        }
                        else if(t == parent->right && sibling->color == BLACK && sibling->right->color == RED && sibling->left->color == BLACK)
                        {
                            sibling->color = RED;
                            sibling->right->color = BLACK;
                            rotateWithLeftChild(sibling);
                        }
                        sibling->color = parent->color;
                        parent->color = BLACK;
                        if(t == parent->left)
                        {
                            sibling->right->color = BLACK;
                            rotateWithLeftChild(parent);
                        }
                        else
                        {
                            sibling->left->color = BLACK;
                            rotateWithRightChild(parent);
                        }
                    }
                }
            }
        }
    protected:
        enum { RED, BLACK };
        Comparable element;
        BinaryNode<Comparable> *root;
        BinaryNode<Comparable> *header;   // The tree header (contains negInf)
        BinaryNode<Comparable> *nullNode;
        BinaryNode<Comparable> *current;
        BinaryNode<Comparable> *parent;
        BinaryNode<Comparable> *grand;
        BinaryNode<Comparable> *successor;
        BinaryNode<Comparable> *great;  
        BinaryNode<Comparable> *sibling;
        BinaryNode<Comparable> * clone(BinaryNode<Comparable> * t) const
        {
            if(t == t->left)  // Cannot test against nullNode!!!
                return nullNode;
            else
                return new BinaryNode<Comparable>{t->element, clone(t->left), clone(t->right), 0, t->color};
        }

        void handleReorient(const Comparable & item)
        {
            current->color = RED;
            current->left->color = BLACK;
            current->right->color = BLACK;
            if( parent->color == RED )   // Have to rotate
            {
                grand->color = RED;
                if( item < grand->element != item < parent->element )
                    parent = rotate( item, grand );  // Start dbl rotate
                current = rotate( item, great );
                current->color = BLACK;
            }
            header->right->color = BLACK; // Make root black
        }

        BinaryNode<Comparable> * rotate( const Comparable & item, BinaryNode<Comparable> *theParent )
        {
            if(item < theParent->element)
            {
                item < theParent->left->element ?
                    rotateWithLeftChild( theParent->left )  :  // LL
                    rotateWithRightChild( theParent->left ) ;  // LR
                return theParent->left;
            }
            else
            {
                item < theParent->right->element ?
                    rotateWithLeftChild( theParent->right ) :  // RL
                    rotateWithRightChild( theParent->right );  // RR
                return theParent->right;
            }
        }
};

template <typename Comparable>
class SplayTree : public BinaryTreeWithRotation<Comparable>
{
    using BinaryTreeWithRotation<Comparable>::rotateWithLeftChild;
    using BinaryTreeWithRotation<Comparable>::rotateWithRightChild;
    public:
        SplayTree()
        {
            nullNode = new BinaryNode<Comparable>;
            nullNode->left = nullNode->right = nullNode;
            root = nullNode;
        }

        SplayTree(const SplayTree & rhs)
        {
            nullNode = new BinaryNode<Comparable>;
            nullNode->left = nullNode->right = nullNode;
            root = clone( rhs.root );
        }

        SplayTree(SplayTree && rhs) :  nullNode{rhs.nullNode} 
        {
            root = rhs.root;
            rhs.root = nullptr;
            rhs.nullNode = nullptr;
        }

        ~SplayTree()
        {
            makeEmpty();
            delete nullNode;
        }

        SplayTree & operator=(const SplayTree & rhs)
        {
            SplayTree copy = rhs;
            std::swap(*this, copy);
            return *this;
        }

        SplayTree & operator=(SplayTree && rhs)
        {
            std::swap(root, rhs.root);
            std::swap(nullNode, rhs.nullNode);
            
            return *this;
        }

        const Comparable & findMin()
        {
            if(isEmpty())
                throw UnderflowException{};
            BinaryNode<Comparable> *ptr = root;
            while(ptr->left != nullNode)
                ptr = ptr->left;
            splay(ptr->element, root);
            return ptr->element;
        }

        const Comparable & findMax()
        {
            if(isEmpty())
                throw UnderflowException{};
            BinaryNode<Comparable> *ptr = root;
            while(ptr->right != nullNode)
                ptr = ptr->right;
            splay(ptr->element, root);
            return ptr->element;
        }

        bool contains(const Comparable & x)
        {
            if(isEmpty())
                return false;
            splay(x, root);
            return root->element == x;
        }

        bool isEmpty( ) const {return root == nullNode;}

        void makeEmpty( )
        {
            while(!isEmpty())
            {
                findMax();        // Splay max item to root
                remove(root->element);
            }
        }

        void insert(const Comparable & x)
        {
            static BinaryNode<Comparable> *newNode = nullptr;

            if(newNode == nullptr)
                newNode = new BinaryNode<Comparable>;
            newNode->element = x;

            if(root == nullNode)
            {
                newNode->left = newNode->right = nullNode;
                root = newNode;
            }
            else
            {
                splay(x, root);
                if(x < root->element)
                {
                    newNode->left = root->left;
                    newNode->right = root;
                    root->left = nullNode;
                    root = newNode;
                }
                else
                if(root->element < x)
                {
                    newNode->right = root->right;
                    newNode->left = root;
                    root->right = nullNode;
                    root = newNode;
                }
                else
                    return;
            }
            newNode = nullptr;   // So next insert will call new
        }

        void remove(const Comparable & x)
        {
            if(!contains(x))
                return;   // Item not found; do nothing
            BinaryNode<Comparable> *newTree;
            if(root->left == nullNode)
                newTree = root->right;
            else
            {
                newTree = root->left;
                splay(x, newTree);
                newTree->right = root->right;
            }
            delete root;
            root = newTree;
        }

    protected:
        BinaryNode<Comparable> *nullNode;
        BinaryNode<Comparable> *root;

        BinaryNode<Comparable> * clone(BinaryNode<Comparable> * t) const
        {
            if(t == t->left)  // Cannot test against nullNode!!!
                return nullNode;
            else
                return new BinaryNode<Comparable>{t->element, clone(t->left), clone(t->right)};
        }

        void splay(const Comparable & x, BinaryNode<Comparable> * & t)
        {
            BinaryNode<Comparable> *leftTreeMax, *rightTreeMin;
            static BinaryNode<Comparable> header;
            header.left = header.right = nullNode;
            leftTreeMax = rightTreeMin = &header;
            nullNode->element = x;   // Guarantee a match
            for( ; ; )
                if(x < t->element)
                {
                    if(x < t->left->element)
                        rotateWithLeftChild(t);
                    if(t->left == nullNode)
                        break;
                    // Link Right
                    rightTreeMin->left = t;
                    rightTreeMin = t;
                    t = t->left;
                }
                else if(t->element < x)
                {
                    if(t->right->element < x)
                        rotateWithRightChild(t);
                    if(t->right == nullNode)
                        break;
                    // Link Left
                    leftTreeMax->right = t;
                    leftTreeMax = t;
                    t = t->right;
                }
                else
                    break;
            leftTreeMax->right = t->left;
            rightTreeMin->left = t->right;
            t->left = header.right;
            t->right = header.left;
        }
};

#endif